Demando P = NP

La interrilato inter la rultempaj komplikecaj klasoj P kaj NP estas nesolvita demando en komputa komplikteorio.

En esenco la demando ĉu P = NP estas jena: se jes-respondo al decida problemo povas esti kontrolita en polinoma tempo, ĉu la respondo povas ankaŭ esti komputita en polinoma tempo?

Decida problemo estas problemo kun respondo jes aŭ ne. Solvado estas en polinoma tempo se ĝi estas farata en maksimume c·n^k paŝoj, kie n estas longo de la enigo kaj k kaj c estas konstantoj sendependaj de la enigo.

Konsideru, ekzemple, la subaran suman problemon, kiu estas ekzemplo de problemo kiu estas facila al kontroli, sed kiu estas kredita (sed ne pruvita) al esti malfacila al komputi. Por donita aro de entjeroj, ĉu estas iu nemalplena subaro de ĝi kies sumo estas 0? La problemo estas decida problemo ĉar la respondo estas jes (la subaro ekzistas) aŭ ne (ne ekzistas). Ekzemple, ĉu estas subaro de la aro {−2, −3, 15, 14, 7, −10} kies sumo estas 0? La respondo estas jesa en ĉi tio okazo, ĉar (−2)+(−3)+15+(−10)=0. Ĝi povas esti rapide kontrolita per kelkaj adicioj. Tamen, trovado de ĉi tia subaro povas preni multe pli longan tempon. La informo bezonata por kontroli pozitivan respondon estas ankaŭ nomata kiel dokumento. Kun donita ĝusta dokumento, la jesa respondo al la problemo povas esti kontrolita en polinoma tempo, tiel la problemo estas en NP.

La demando ĉu P = NP demando devas difini ĉu problemoj similaj al la subara suma problemo estas facile (en polinoma tempo) komputeblaj. Se P ≠ NP, do iuj NP problemoj estas signife "pli pezaj" por komputi ol por kontroli.

La limigo al jes/ne problemoj estas negrava; la rezultanta problemo kun pli komplika respondo estas permesata, la demando ĉu FP = FNP estas ekvivalenta al ĉu P = NP.^[1]

1. ↑ Scott Aaronson. Komplikeca zoo: FP. "FP = FNP se kaj nur se P = NP". http://qwiki.stanford.eduview_html.php?sq=Google&lang=eo&q=Complexity_Zoo#fp Arkivigite je 2010-07-26 per la retarkivo Wayback Machine